package 我的Java学习_算法基础.day_05;

import static 我的Java学习_算法基础.day_05._084_字符串匹配之后缀数组_上.getSa1;
import static 我的Java学习_算法基础.day_05._085_字符串匹配之后缀数组_中.getSa2;

public class _084_后缀数组匹配 {
    public static void main(String[] args) {
        String a = "ABAAABABB", b = "BABB";
        System.out.println(match2(a, b));
    }

    private static void match0(String s1, String key) {
        String s = s1;
        String p = key;
        Suff[] sa = getSa1(s);
        int l = 0;
        int r = s.length() - 1;
        //二分查找 N*lgM
        while (r >= 1) {
            int mid = l + ((r - l) >> 1);
            //居中的后缀
            Suff midSuff = sa[mid];
            String suffStr = midSuff.str;
            int compareRes;
            //将后缀和模式串比较O(N)
            //B大于A
            if (suffStr.length() >= p.length()) {
                compareRes = suffStr.substring(0, p.length()).compareTo(p);
            } else {
                compareRes = suffStr.compareTo(p);
            }
            if (compareRes == 0) {
                System.out.println(midSuff.index);
                break;
            } else if (compareRes < 0) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
    }

    /**
     * 粗暴后缀数组法
     * @param s 原串
     * @param key 目标串
     * @return
     */
    private static int match1(String s, String key){
        return match_1(s,key,0,s.length()-1);
    }
    private static int match_1(String s, String key, int l, int r) {
        if (l > r) {
            return -1;
        }
        Suff[] sa = getSa1(s);

        //二分查找 N*lgM
        int mid = l + ((r - l) >> 1);
        //居中的后缀
        Suff midSuff = sa[mid];
        String suffStr = midSuff.str;
        int compareRes;
        //将后缀和模式串比较O(N)
        //B大于A
        if (suffStr.length() >= key.length()) {
            compareRes = suffStr.substring(0, key.length()).compareTo(key);
        } else {
            compareRes = suffStr.compareTo(key);
        }
        if (compareRes == 0) {
            return midSuff.index;
        } else if (compareRes < 0) {
            return match_1(s, key, mid + 1, r);
        } else {
            return match_1(s, key, l, mid - 1);
        }
    }

    /***
     * 倍增求后缀数组法
     * @param s 原串
     * @param key 目标串
     * @return
     */
    private static int match2(String s, String key){
        return match_2(s,key,0,s.length()-1);
    }
    private static int match_2(String s, String key, int l, int r) {
        if (l > r) {
            return -1;
        }
        Suff[] sa = getSa2(s);

        //二分查找 N*lgM
        int mid = l + ((r - l) >> 1);
        //居中的后缀
        Suff midSuff = sa[mid];
        String suffStr = midSuff.str;
        int compareRes;
        //将后缀和模式串比较O(N)
        //B大于A
        if (suffStr.length() >= key.length()) {
            compareRes = suffStr.substring(0, key.length()).compareTo(key);
        } else {
            compareRes = suffStr.compareTo(key);
        }
        if (compareRes == 0) {
            return midSuff.index;
        } else if (compareRes < 0) {
            return match_2(s, key, mid + 1, r);
        } else {
            return match_2(s, key, l, mid - 1);
        }
    }

}
